HW#4 --- last modified February 06 2019 04:20:39..

Solution set.

Due date: Apr 20

Files to be submitted:
  Hw4.zip

Purpose: To learn about randomized online algorithms. To learn about modular arithmetic algorithms.

Related Course Outcomes:

LO6 -- Analyze or code a number theoretic algorithm

The main course outcomes covered by this assignment are:

Specification:

This homework consists of three short coding assignments which should all be submitted in Hw4.zip. The first program I want you to write is Marker.java. This program should implement the marker algorithm for the paging problem discussed in class. It will be compiled from the command line with the following command:

javac Marker.java

It will then be run using a line like:

java Marker cache_size

For example,

java Marker 5

Marker then will create a cache of size cache_size and initialize the pages in this cache to be 1,2,3 ... cache_size. For the example just given, 1, 2, 3, 4, 5. It will then draw the current cache, prompt the user for a page request, and repeat. When a cache miss occurs it will use the marker algorithm to decide which page to eject. A page request can be any positive integer. If a request is for a negative integer the program stops. For example,

java Marker 5
Cache Looks Like
1
2
3
4
5
What page would you like? 20
Cache Looks Like
20 X
2
3
4
5
What page would you like? -1
Done

The X in the above indicates a marked page. For the second program, I want you to implement the extended Euclidean algorithm in a file ExtendedEuclidean.java. This will also be compiled from the command line with a single line like above. Your program will then be run with a line like:

java ExtendedEuclidean x y

where x and y are two integers. On this input it will then output the results of the extended Euclidean algorithm. For example,

java ExtendedEuclidean 15 2
(1,1,-7)

The last program for this homework will be called ChineseRemainder.java. It will again be compiled from the command line in the same fashion as the first program. After which it will be run with a command like:

java ChineseRemainder a_0 n_0 a_1 n_1 ... a_n n_m

Here `0 le a_i < n_i`. The goal is to compute a number `a mod n_1 cdot n_2 cdots n_m` such that `a equiv a_i mod n_i` for each `i`. For example, the problem we went over in class could be entered as

java ChineseRemainder 1 2 2 3 3 5

On which your program should output

The Chinese Remainder is:
23

Point Breakdown